package com.example.sword.sword;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 链表
 *
 * 倒数第k个值
 */
public class Test22 {
    public static void main(String[] args) {
        ListNode node6=new   ListNode(6,null);
        ListNode node5 =new   ListNode(5,node6);
        ListNode node4 =new   ListNode(4,node5);
        ListNode root =new   ListNode(1,node4);
        System.out.println(getReverseValue(root, 2));
    }
//  标准解法
//    ArrayDeque 陷入先出队列，超过k就先弹出头，在添加尾巴 ，返回对列的尾巴就是第k小的值
    public static int  getReverseValue(ListNode root, int k) {
        Deque<Integer> last =new ArrayDeque<>(k);
        while(root.next != null ) {
            if (last.size() == k) {
                last.pop();
            }
            last.push(root.value);
            root = root.next;
        }
        return last.peek();
    }


    public static class ListNode {
        private int value;
        private ListNode next;

        public ListNode(int value,  ListNode next) {
            this.value = value;
            this.next = next;
        }
    }

}
